from typing import List

# 贪心
# 若当前指针所指元素的和小于0，则丢弃当前元素之前的数列
# 官方解答是这个，它算作动态规划
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        # 这个可以去掉
        if not nums: return -2147483648
        cur_sum = max_sum = nums[0]
        # 可以不从1开始
        for i in range(1, len(nums)):
            cur_sum = max(nums[i], cur_sum+nums[i])
            max_sum = max(cur_sum, max_sum)

        return max_sum

# 动态规划
# 若前一个元素大于0，则将其加到当前元素上
class Solution2:
    def maxSubArray(self, nums: List[int]) -> int:
        n = len(nums)
        for i in range(1, n):
            if nums[i-1] > 0:
                nums[i] += nums[i-1]
        return max(nums)

# 分治：暂时没有python的，不懂，看其它语言的